const common = require('./base/common');

/**
 * 1449. 数位成本和为目标值的最大数字
 * 
 * @param {*} cost 费用列表
 * @param {*} target 目标
 * @returns 
 */
var largestNumber = function(cost, target) {
    // f 表示：在某个费用j上最长的长度
    let t = target, f = new Array(t + 1).fill(-Infinity);
    f[0] = 0;
    for (let i = 1; i <= 9; i++) {
        let u = cost[i - 1];
        // 计算某个费用f[j]与f[j-u] + 1中最长的
        for (let j = u; j <= t; j++) {
            f[j] = Math.max(f[j], f[j - u] + 1);
        }
    }

    // 直到t也无法凑出长度则返回0
    if (f[t] < 0) return "0";

    let ans = "";
    // 从高往低取
    for (let i = 9, j = t; i >= 1; i--) {
        let u = cost[i - 1];
        // 1. 费用 j >= u，保证 j - u >= 0
        // 2. 保证长度匹配
        while (j >= u && f[j] == f[j - u] + 1) {
            ans += i;
            j -= u;
        }
    }
    return ans;
};

common.testing([
    [[4,3,2,5,6,7,2,5,5], 9],
    [[2,4,6,2,4,6,4,4,4], 5],
    [[5,6,7,3,4,6,7,4,8], 29]
], ["7772", "0", "884444444"])(x => largestNumber(x[0], x[1]));